home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 2 / Apprentice-Release2.iso / Source Code / C / Libraries / Berkeley DB 1.6 / hash / hash_buf.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-07-27  |  8.8 KB  |  345 lines  |  [TEXT/????]
  1. /*-
  2.  * Copyright (c) 1990, 1993
  3.  *    The Regents of the University of California.  All rights reserved.
  4.  *
  5.  * This code is derived from software contributed to Berkeley by
  6.  * Margo Seltzer.
  7.  *
  8.  * Redistribution and use in source and binary forms, with or without
  9.  * modification, are permitted provided that the following conditions
  10.  * are met:
  11.  * 1. Redistributions of source code must retain the above copyright
  12.  *    notice, this list of conditions and the following disclaimer.
  13.  * 2. Redistributions in binary form must reproduce the above copyright
  14.  *    notice, this list of conditions and the following disclaimer in the
  15.  *    documentation and/or other materials provided with the distribution.
  16.  * 3. All advertising materials mentioning features or use of this software
  17.  *    must display the following acknowledgement:
  18.  *    This product includes software developed by the University of
  19.  *    California, Berkeley and its contributors.
  20.  * 4. Neither the name of the University nor the names of its contributors
  21.  *    may be used to endorse or promote products derived from this software
  22.  *    without specific prior written permission.
  23.  *
  24.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  25.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  26.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  28.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  29.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  30.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  31.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  33.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  34.  * SUCH DAMAGE.
  35.  */
  36.  
  37. #if defined(LIBC_SCCS) && !defined(lint)
  38. static char sccsid[] = "@(#)hash_buf.c    8.1 (Berkeley) 6/4/93";
  39. #endif /* LIBC_SCCS and not lint */
  40.  
  41. /*
  42.  * PACKAGE: hash
  43.  *
  44.  * DESCRIPTION:
  45.  *    Contains buffer management
  46.  *
  47.  * ROUTINES:
  48.  * External
  49.  *    __buf_init
  50.  *    __get_buf
  51.  *    __buf_free
  52.  *    __reclaim_buf
  53.  * Internal
  54.  *    newbuf
  55.  */
  56.  
  57. #include <sys/param.h>
  58.  
  59. #include <errno.h>
  60. #include <stdio.h>
  61. #include <stdlib.h>
  62. #ifdef DEBUG
  63. #include <assert.h>
  64. #endif
  65.  
  66. #include <db.h>
  67. #include "hash.h"
  68. #include "page.h"
  69. #include "extern.h"
  70.  
  71. static BUFHEAD *newbuf __P((HTAB *, u_int, BUFHEAD *));
  72.  
  73. /* Unlink B from its place in the lru */
  74. #define BUF_REMOVE(B) { \
  75.     (B)->prev->next = (B)->next; \
  76.     (B)->next->prev = (B)->prev; \
  77. }
  78.  
  79. /* Insert B after P */
  80. #define BUF_INSERT(B, P) { \
  81.     (B)->next = (P)->next; \
  82.     (B)->prev = (P); \
  83.     (P)->next = (B); \
  84.     (B)->next->prev = (B); \
  85. }
  86.  
  87. #define    MRU    hashp->bufhead.next
  88. #define    LRU    hashp->bufhead.prev
  89.  
  90. #define MRU_INSERT(B)    BUF_INSERT((B), &hashp->bufhead)
  91. #define LRU_INSERT(B)    BUF_INSERT((B), LRU)
  92.  
  93. /*
  94.  * We are looking for a buffer with address "addr".  If prev_bp is NULL, then
  95.  * address is a bucket index.  If prev_bp is not NULL, then it points to the
  96.  * page previous to an overflow page that we are trying to find.
  97.  *
  98.  * CAVEAT:  The buffer header accessed via prev_bp's ovfl field may no longer
  99.  * be valid.  Therefore, you must always verify that its address matches the
  100.  * address you are seeking.
  101.  */
  102. extern BUFHEAD *
  103. __get_buf(hashp, addr, prev_bp, newpage)
  104.     HTAB *hashp;
  105.     u_int addr;
  106.     BUFHEAD *prev_bp;
  107.     int newpage;    /* If prev_bp set, indicates a new overflow page. */
  108. {
  109.     register BUFHEAD *bp;
  110.     register u_int is_disk_mask;
  111.     register int is_disk, segment_ndx;
  112.     SEGMENT segp;
  113.  
  114.     is_disk = 0;
  115.     is_disk_mask = 0;
  116.     if (prev_bp) {
  117.         bp = prev_bp->ovfl;
  118.         if (!bp || (bp->addr != addr))
  119.             bp = NULL;
  120.         if (!newpage)
  121.             is_disk = BUF_DISK;
  122.     } else {
  123.         /* Grab buffer out of directory */
  124.         segment_ndx = addr & (hashp->SGSIZE - 1);
  125.  
  126.         /* valid segment ensured by __call_hash() */
  127.         segp = hashp->dir[addr >> hashp->SSHIFT];
  128. #ifdef DEBUG
  129.         assert(segp != NULL);
  130. #endif
  131.         bp = PTROF(segp[segment_ndx]);
  132.         is_disk_mask = ISDISK(segp[segment_ndx]);
  133.         is_disk = is_disk_mask || !hashp->new_file;
  134.     }
  135.  
  136.     if (!bp) {
  137.         bp = newbuf(hashp, addr, prev_bp);
  138.         if (!bp ||
  139.             __get_page(hashp, bp->page, addr, !prev_bp, is_disk, 0))
  140.             return (NULL);
  141.         if (!prev_bp)
  142.             segp[segment_ndx] =
  143.                 (BUFHEAD *)((u_int)bp | is_disk_mask);
  144.     } else {
  145.         BUF_REMOVE(bp);
  146.         MRU_INSERT(bp);
  147.     }
  148.     return (bp);
  149. }
  150.  
  151. /*
  152.  * We need a buffer for this page. Either allocate one, or evict a resident
  153.  * one (if we have as many buffers as we're allowed) and put this one in.
  154.  *
  155.  * If newbuf finds an error (returning NULL), it also sets errno.
  156.  */
  157. static BUFHEAD *
  158. newbuf(hashp, addr, prev_bp)
  159.     HTAB *hashp;
  160.     u_int addr;
  161.     BUFHEAD *prev_bp;
  162. {
  163.     register BUFHEAD *bp;        /* The buffer we're going to use */
  164.     register BUFHEAD *xbp;        /* Temp pointer */
  165.     register BUFHEAD *next_xbp;
  166.     SEGMENT segp;
  167.     int segment_ndx;
  168.     u_short oaddr, *shortp;
  169.  
  170.     oaddr = 0;
  171.     bp = LRU;
  172.     /*
  173.      * If LRU buffer is pinned, the buffer pool is too small. We need to
  174.      * allocate more buffers.
  175.      */
  176.     if (hashp->nbufs || (bp->flags & BUF_PIN)) {
  177.         /* Allocate a new one */
  178.         bp = malloc(sizeof(struct _bufhead));
  179.         if (!bp || !(bp->page = malloc(hashp->BSIZE)))
  180.             return (NULL);
  181.         if (hashp->nbufs)
  182.             hashp->nbufs--;
  183.     } else {
  184.         /* Kick someone out */
  185.         BUF_REMOVE(bp);
  186.         /*
  187.          * If this is an overflow page with addr 0, it's already been
  188.          * flushed back in an overflow chain and initialized.
  189.          */
  190.         if ((bp->addr != 0) || (bp->flags & BUF_BUCKET)) {
  191.             /*
  192.              * Set oaddr before __put_page so that you get it
  193.              * before bytes are swapped.
  194.              */
  195.             shortp = (u_short *)bp->page;
  196.             if (shortp[0])
  197.                 oaddr = shortp[shortp[0] - 1];
  198.             if ((bp->flags & BUF_MOD) && __put_page(hashp, bp->page,
  199.                 bp->addr, (int)IS_BUCKET(bp->flags), 0))
  200.                 return (NULL);
  201.             /*
  202.              * Update the pointer to this page (i.e. invalidate it).
  203.              *
  204.              * If this is a new file (i.e. we created it at open
  205.              * time), make sure that we mark pages which have been
  206.              * written to disk so we retrieve them from disk later,
  207.              * rather than allocating new pages.
  208.              */
  209.             if (IS_BUCKET(bp->flags)) {
  210.                 segment_ndx = bp->addr & (hashp->SGSIZE - 1);
  211.                 segp = hashp->dir[bp->addr >> hashp->SSHIFT];
  212. #ifdef DEBUG
  213.                 assert(segp != NULL);
  214. #endif
  215.  
  216.                 if (hashp->new_file &&
  217.                     ((bp->flags & BUF_MOD) ||
  218.                     ISDISK(segp[segment_ndx])))
  219.                     segp[segment_ndx] = (BUFHEAD *)BUF_DISK;
  220.                 else
  221.                     segp[segment_ndx] = NULL;
  222.             }
  223.             /*
  224.              * Since overflow pages can only be access by means of
  225.              * their bucket, free overflow pages associated with
  226.              * this bucket.
  227.              */
  228.             for (xbp = bp; xbp->ovfl;) {
  229.                 next_xbp = xbp->ovfl;
  230.                 xbp->ovfl = 0;
  231.                 xbp = next_xbp;
  232.  
  233.                 /* Check that ovfl pointer is up date. */
  234.                 if (IS_BUCKET(xbp->flags) ||
  235.                     (oaddr != xbp->addr))
  236.                     break;
  237.  
  238.                 shortp = (u_short *)xbp->page;
  239.                 if (shortp[0])
  240.                     /* set before __put_page */
  241.                     oaddr = shortp[shortp[0] - 1];
  242.                 if ((xbp->flags & BUF_MOD) && __put_page(hashp,
  243.                     xbp->page, xbp->addr, 0, 0))
  244.                     return (NULL);
  245.                 xbp->addr = 0;
  246.                 xbp->flags = 0;
  247.                 BUF_REMOVE(xbp);
  248.                 LRU_INSERT(xbp);
  249.             }
  250.         }
  251.     }
  252.  
  253.     /* Now assign this buffer */
  254.     bp->addr = addr;
  255. #ifdef DEBUG1
  256.     (void)fprintf(stderr, "NEWBUF1: %d->ovfl was %d is now %d\n",
  257.         bp->addr, (bp->ovfl ? bp->ovfl->addr : 0), 0);
  258. #endif
  259.     bp->ovfl = NULL;
  260.     if (prev_bp) {
  261.         /*
  262.          * If prev_bp is set, this is an overflow page, hook it in to
  263.          * the buffer overflow links.
  264.          */
  265. #ifdef DEBUG1
  266.         (void)fprintf(stderr, "NEWBUF2: %d->ovfl was %d is now %d\n",
  267.             prev_bp->addr, (prev_bp->ovfl ? bp->ovfl->addr : 0),
  268.             (bp ? bp->addr : 0));
  269. #endif
  270.         prev_bp->ovfl = bp;
  271.         bp->flags = 0;
  272.     } else
  273.         bp->flags = BUF_BUCKET;
  274.     MRU_INSERT(bp);
  275.     return (bp);
  276. }
  277.  
  278. extern void
  279. __buf_init(hashp, nbytes)
  280.     HTAB *hashp;
  281.     int nbytes;
  282. {
  283.     BUFHEAD *bfp;
  284.     int npages;
  285.  
  286.     bfp = &(hashp->bufhead);
  287.     npages = (nbytes + hashp->BSIZE - 1) >> hashp->BSHIFT;
  288.     npages = MAX(npages, MIN_BUFFERS);
  289.  
  290.     hashp->nbufs = npages;
  291.     bfp->next = bfp;
  292.     bfp->prev = bfp;
  293.     /*
  294.      * This space is calloc'd so these are already null.
  295.      *
  296.      * bfp->ovfl = NULL;
  297.      * bfp->flags = 0;
  298.      * bfp->page = NULL;
  299.      * bfp->addr = 0;
  300.      */
  301. }
  302.  
  303. extern int
  304. __buf_free(hashp, do_free, to_disk)
  305.     HTAB *hashp;
  306.     int do_free, to_disk;
  307. {
  308.     BUFHEAD *bp;
  309.  
  310.     /* Need to make sure that buffer manager has been initialized */
  311.     if (!LRU)
  312.         return (0);
  313.     for (bp = LRU; bp != &hashp->bufhead;) {
  314.         /* Check that the buffer is valid */
  315.         if (bp->addr || IS_BUCKET(bp->flags)) {
  316.             if (to_disk && (bp->flags & BUF_MOD) &&
  317.                 __put_page(hashp, bp->page,
  318.                 bp->addr, IS_BUCKET(bp->flags), 0))
  319.                 return (-1);
  320.         }
  321.         /* Check if we are freeing stuff */
  322.         if (do_free) {
  323.             if (bp->page)
  324.                 free(bp->page);
  325.             BUF_REMOVE(bp);
  326.             free(bp);
  327.             bp = LRU;
  328.         } else
  329.             bp = bp->prev;
  330.     }
  331.     return (0);
  332. }
  333.  
  334. extern void
  335. __reclaim_buf(hashp, bp)
  336.     HTAB *hashp;
  337.     BUFHEAD *bp;
  338. {
  339.     bp->ovfl = 0;
  340.     bp->addr = 0;
  341.     bp->flags = 0;
  342.     BUF_REMOVE(bp);
  343.     LRU_INSERT(bp);
  344. }
  345.